/************************************************************************

								Heroes IV
					  Copyright 2000, The 3DO Company

	------------------------------------------------------------------
  						      palette_creator.h

	$Header: /resource_editor/palette_creator.h $

	$NoKeywords: $

 ************************************************************************/
// kill the 255+ character identifier warning.  Templates tend to exceed that easily.
#include "precompiled.h"
#pragma warning( disable: 4786 )

#include "palette_creator.h"

#include "color_cube.h"
#include "pixel_24.h"

//------------------------------------------------------------
// palette_creator.cpp
//------------------------------------------------------------
t_color_count* t_palette_creator::find( t_pixel_24 const& pixel, 
									    bool create_if_missing )
{
	int key_value = (pixel.red << 16) | (pixel.green << 8) | pixel.blue;
	int index = key_value % k_hash_size;
	int upper;
	int lower;
	int mid;
	t_color_count* result;

	index = index % k_hash_size;
	upper = m_hash_table[index].size();
	lower = 0;
	while (true)
	{
		mid = (upper + lower) >> 1;
		if( upper <= lower )
			break;
		result = m_hash_table[index][mid];
		if ( ((result->color[k_red_axis] << 16) | (result->color[k_green_axis] << 8)
			| result->color[k_blue_axis]) < key_value)
			lower = mid + 1;
		else
			upper = mid;
	}
	if (mid >= m_hash_table[index].size()
		|| m_hash_table[index][mid]->color[k_red_axis] != pixel.red
		|| m_hash_table[index][mid]->color[k_green_axis] != pixel.green
		|| m_hash_table[index][mid]->color[k_blue_axis] != pixel.blue)
	{
		if (!create_if_missing)
			return 0;

		result = new t_color_count( pixel );
		m_colors.push_back( result );
		m_hash_table[index].insert( m_hash_table[index].begin() + mid, result );
		return result;
	}
	return m_hash_table[index][mid];
}

//------------------------------------------------------------
// create colors for the reserved indexes
//------------------------------------------------------------
void t_palette_creator::set_reserved_colors( int reserved_colors )
{
	// find unused colors for each reserved index
	bool found;
	int  i, j;
	t_pixel_24 pixel(248,248,248);

	// start at -8,-8,-8, so first tested color is black(0,0,0)
	for (i = 0; i < reserved_colors; i++)
	{
		do
		{
			// add 8 to blue
			pixel.blue += 8;
			if (pixel.blue == 0) // if overflow, add 8 to green
			{
				pixel.green += 8;
				if (pixel.green == 0) // if overflow, add 8 to red
					pixel.red += 8;
			}
			// look through all colors to see if one is within 8 in all
			// channels - we don't want to have the same color on
			// 16 bit displays, which drop the least 3 bits of each channel
			found = true;
			for (j = reserved_colors; j < m_palette.size(); j++)
			{
				if (abs( pixel.red - m_palette[j].red ) < 8
					&& abs( pixel.green - m_palette[j].green) < 8
					&& abs( pixel.blue - m_palette[j].blue ) < 8)
				{
					found = false;
					break;
				}
			}
		} while (!found);
		m_palette[i] = pixel;
	}
}

//------------------------------------------------------------
// create an optimized palette of a given # of colors from the color information
//------------------------------------------------------------
void t_palette_creator::create( int max_colors, int reserved_colors, bool force_creation )
{
	int        i, j;
	int        color_count = m_colors.size();
	t_pixel_24 pixel;

	if (color_count <= max_colors && !force_creation)
	{   // few enough unique colors that we can use an exact palette.
		t_color_count_list::iterator index;
		
		i = reserved_colors;
		m_palette.resize( color_count + reserved_colors );
		for (index = m_colors.begin(); index != m_colors.end(); index++)
		{
			m_palette[i] = t_pixel_24( (*index)->color[k_red_axis], 
							           (*index)->color[k_green_axis],
									   (*index)->color[k_blue_axis] );
			(*index)->index = i++;
		}
	}
	else
	{
		std::vector<int> search_nodes;
		t_color_tree     search_node;

		// make enough cubes to accomodate all the desired colors.
		m_cubes.resize( max_colors );
		{
			// copy the colors into an array
			std::vector<t_color_count_ptr> color_array;
			t_color_count_list::iterator   source;

			color_array.reserve( color_count );
			for (source = m_colors.begin(); source != m_colors.end(); source++)
				color_array.push_back( *source );

			m_cubes[0].init( color_array );
			// color array will now go out of scope
			search_node.is_leaf = true;
			search_node.value = reserved_colors;
			m_color_tree.push_back( search_node );
			search_nodes.push_back( 0 );
		}

		int largest;
		t_axis axis;

		for (i = 1; i < max_colors; i++)
		{
			largest = 0;
			for (j = 0; j < i; j++)
			{
				if (m_cubes[j].get_variance() > m_cubes[largest].get_variance())
					largest = j;
			}
			if (m_cubes[largest].get_variance() == 0)
				break;
			axis = m_cubes[largest].cut( m_cubes[i] );

			// push back new leaf
			int greater_node = m_color_tree.size();
			search_node.is_leaf = true;
			search_node.value = i + reserved_colors;
			m_color_tree.push_back( search_node );
			search_nodes.push_back( greater_node );

			// move old leaf
			int branch_node = search_nodes[largest];
			int lesser_node = m_color_tree.size();

			search_node = m_color_tree[branch_node];
			m_color_tree.push_back( search_node );
			search_nodes[largest] = lesser_node;

			// make branch
			search_node.is_leaf = false;
			search_node.axis = axis;
			search_node.greater_or_equal = greater_node;
			search_node.less_than = lesser_node;
			search_node.value = m_cubes[i].get_min_color( axis );
			m_color_tree[branch_node] = search_node;
		}
		max_colors = i;
		m_palette.resize( max_colors + reserved_colors );
		for (i = 0; i < max_colors; i++)
		{
			m_palette[i + reserved_colors] = m_cubes[i].get_average();
			m_cubes[i].set_indexes( i + reserved_colors );
		}
	}
	set_reserved_colors( reserved_colors );
}

//------------------------------------------------------------
// get a given palette index, give a color
//------------------------------------------------------------
int t_palette_creator::get_index( t_pixel_24 const& pixel )
{
	t_color_count* color_count = find( pixel, true );

	if (color_count->count == 0)
	{
		int colors[3];

		colors[k_red_axis] = pixel.red;
		colors[k_green_axis] = pixel.green;
		colors[k_blue_axis] = pixel.blue;

		// find in the cubes
		int index = 0;
		t_color_tree search_node;

		while (true)
		{
			search_node = m_color_tree[index];
			if (search_node.is_leaf)
				break;
			if (colors[search_node.axis] >= search_node.value)
				index = search_node.greater_or_equal;
			else
				index = search_node.less_than;
		}
		color_count->index = search_node.value;
		color_count->count++;
	}
	return color_count->index;
}
